UVa/11338 - Minefield/11338.clean.cpp

   1 #include <iostream>
   2 #include <vector>
   3 #include <queue>
   4 #include <map>
   5 #include <cmath>
   6 #include <sstream>
   7 #include <functional>
   8
   9 using namespace std;
  10
  11 const double infinity = 1E20;
  12
  13 //I'm representing a node as a point with X and Y coordinates.
  14 struct point{
  15   double x, y;
  16   point(double X, double Y){ x = X; y = Y;}
  17 };
  18
  19 //This map holds the best distance seen from the start node in Dijkstra's algorithm
  20 map< point, double > dist;
  21
  22 //Some operator for the points
  23 bool operator ==(const point &a, const point &b){ return (a.x == b.x && a.y == b.y);}
  24 bool operator !=(const point &a, const point &b){ return !(a == b);}
  25 bool operator <(const point &a, const point &b){ return (a.x < b.x || (a.x == b.x && a.y < b.y));}
  26 //This returns the Euclidean distance between two points
  27 double euclidean(point a, point b){return hypot(a.y-b.y, a.x-b.x);}
  28
  29
  30 //This is used as a "sort class" for the priority_queue used by Dijkstra's algorithm.
  31 //It simply sorts the points in the priority_queue by less dist[x].
  32 //i.e, the top of the priority_queue always has the point with smaller dist.
  33 struct heapCompare : public binary_function<point, point, bool>
  34 {
  35   bool operator()(const point &x, const point &y) const
  36   { return dist[x] > dist[y]; }
  37 };
  38
  39
  40 struct graph{
  41   //This holds ALL nodes without relating them to their neighbors, i.e, all nodes alone
  42   //This is used to keep track of what nodes are present in the map neigbors.
  43   vector<point> nodes;
  44
  45   //This holds a vector of all adjacent points for a given point
  46   //Adjacent points of a point X are those who are not further than 1.5 from X
  47   map< point, vector<point> > neighbors;
  48
  49   //This function inserts a new node into the graph.
  50   void insert(const point &a){
  51     //First check if the node is allready present.
  52     if (find(nodes.begin(), nodes.end(), a) != nodes.end()) return;
  53     //Insert the node
  54     nodes.push_back(a);
  55     //Now we are going to insert it as a neighbor of all other nodes with are at most 1.5 away from him
  56     for (int i=0; i<nodes.size(); ++i){
  57       //A node can't be neighbor of himself:
  58       if (nodes[i] != a){
  59         vector<point> adj = neighbors[nodes[i]];
  60         //Make sure the node hasn't been inserted before.
  61         //In theory, this should ALWAYS be true.
  62         if (find(adj.begin(), adj.end(), a) == adj.end()){
  63           //If is close enough...
  64           if (euclidean(a, nodes[i]) < 1.5){
  65             //Insert it in both neighbors vectors (The graph is non-directed).
  66             neighbors[nodes[i]].push_back(a);
  67             neighbors[a].push_back(nodes[i]);
  68           }
  69         }
  70       }
  71     }
  72   }
  73
  74   //This initializes things needed by Dijkstra's algorithm.
  75   void initialize(){
  76     //We need a fresh map for every graph, and since dist is a global variable we have to clean it
  77     dist.clear();
  78     //Set dist of all nodes to infinity except for the starting node.
  79     for (int i=0; i<nodes.size(); ++i){
  80       dist[nodes[i]] = infinity;
  81     }
  82     dist[point(0.0, 0.0)] = 0.00;
  83   }
  84
  85   //maxPath is the restriction given in the problem statement (d).
  86   //finalPoint is where we want to get.
  87   void dijkstra(const double &maxPath, const point &finalPoint){
  88
  89     initialize();
  90
  91     //Used to get the point with less dist from all reachable points.
  92     priority_queue<point, vector<point>, heapCompare > q;
  93     //We always start at the origin
  94     q.push(point(0.0, 0.0));
  95
  96     while (!q.empty()){
  97       point u = q.top();
  98       q.pop();
  99       //Do not visit a node if it's not even possible to reach it within the given constraint in straight line.
 100       if (euclidean(point(0.00, 0.00), u) + euclidean(u, finalPoint) <= maxPath){
 101         for (int i=0; i<neighbors[u].size(); ++i){
 102           point v = neighbors[u][i];
 103           //Relax
 104           if (dist[neighbors[u][i]] > (dist[u] + euclidean(u,v))){
 105             dist[neighbors[u][i]] = dist[u] + euclidean(u, v);
 106             //Push reachable node into the queue.
 107             q.push(v);
 108           }
 109         }
 110       }
 111     }
 112   }
 113 };
 114
 115
 116
 117 int main(){
 118   while (true){
 119
 120     //Lame code to check if we got an '*'
 121     string s;
 122     for (s = ""; s == ""; getline(cin, s));
 123     if (s == "*") break;
 124
 125
 126     graph g;
 127
 128     stringstream line;
 129     line << s;
 130
 131     int w,h;
 132     //Read the coordinates of the final point
 133     line >> w >> h;
 134
 135     //Insert the final and starting point
 136     g.insert(point((double)w, (double)h));
 137     g.insert(point(0.00, 0.00));
 138
 139     //Quantity of points
 140     int noPoints;
 141     cin >> noPoints;
 142     //Read each point and insert it
 143     for (int i=0; i<noPuntos; ++i){
 144       double x,y;
 145       cin >> x >> y;
 146       g.insert(point(x,y));
 147     }
 148
 149     //Read the maximum path's length.
 150     double maxPath;
 151     cin >> maxPath;
 152
 153     g.dijkstra(maxPath, point((double)w, (double)h));
 154
 155     if (dist[point((double)w, (double)h)] < maxPath){
 156       printf("I am lucky!\n");
 157     }else{
 158       printf("Boom!\n");
 159     }
 160
 161   }
 162   return 0;
 163 }